
#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);//采用了随机选择



int kthBiggest(int arr[], int l, int r, int k)//设定k所在的数组
{
    
    if (k > 0 && k <= r - l + 1)
    {
        
        int pos = randomPartition(arr, l, r);

        
        if (pos - l == k - 1)
            return arr[pos];
        if (pos - l > k - 1)  
            return kthBiggest(arr, l, pos - 1, k);

        
        return kthBiggest(arr, pos + 1, r, k - pos + l - 1);
    }

    return INT_MIN;
}
//交换 
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)//时间复杂度o(n) 
    {
        if (arr[j] > x)
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]);
    return i;
}


int randomPartition(int arr[], int l, int r)
{
    int n = r - l + 1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return partition(arr, l, r);
}


int main()
{
    int a[] = { 8, -3, -4, -6, 4, 3, 7, -1, 1, 0, 20, -11, -13, 14, 12, 11 };//定义数组元素 
    int n = (a, sizeof(a) / sizeof(int));
    cout << "K'th biggest element is " << kthBiggest(a, 0, n - 1, 2);//输出第k大数据 
    return 0;
}
